package name.huzhenbo.java.algorithm.graph;

import java.util.*;

/**
 * DLJ is the person who found this algorithm.
 *
 * Find out the shortest path to all of the other vertexs from a specific vertex.
 *
 * O(n2)
 *
 * So, the complexity is O(n3) for find out the shortest paths for all pairs.
 */
class DLJShortestPath {
    private Map<Integer, Path> paths;
    private Graph graph;
    private int from;
    private List<Integer> doneVexes;

    public DLJShortestPath(Graph graph, int from) {
        this.graph = graph;
        this.from = from;
        doneVexes = new ArrayList<Integer>();
    }

    public Path to(int target) {
        if (paths == null) {
            paths = new HashMap<Integer, Path>();
            search();
        }
        return paths.get(target);
    }

    private void search() {
        while (true) {
            Path currentShortest = currentShortestInUndone();
            if (currentShortest == null) {
                // no more found, means all of the vertexes have been included
                break;
            } else {
                // the end of current shortest path is a new founded path
                // it must be the shortest path from start to this end, because all the other paths are longer than it
                // e.g. a graph with 5 vexes. THe path start from 0, and current end is 3, and
                // [0, 1] is 30
                // [0, 2] is 40
                // [0, 4, 3] is 20, where [0, 4] is 15
                // then [0, 4, 3] must be the shortest path to 3
                doneVexes.add(currentShortest.end());
            }
            updatePaths(currentShortest);
        }
    }

    // e.g. a graph with 5 vexes. The path start from 0
    // [0, 1] is 30
    // [0, 2] is 40
    // [0, 4] is 15
    // then 4 is done
    // then [0, 4] is previous shortest
    // expand from 4, because next shortest must in [0, 1], [0, 2] and the extention from 4
    // e.g, if found
    // [0, 4, 3] is 20
    // then 3 is next shortest
    private void updatePaths(Path previousShortest) {
        int currentFrom = previousShortest.end();
        int currentVex = graph.firstAdjVex(currentFrom);
        while (currentVex != -1) {
            int newDistance = previousShortest.getDistance() + graph.weight(currentFrom, currentVex);
            if (paths.get(currentVex) == null || newDistance < paths.get(currentVex).getDistance())
                paths.put(currentVex, new Path(extendPath(previousShortest.getPath(), currentVex), newDistance));
            currentVex = graph.nextAdjVex(currentFrom, currentVex);
        }
    }

    private int[] extendPath(int[] path, int currentVex) {
        int[] newPath = Arrays.copyOf(path, path.length + 1);
        newPath[path.length] = currentVex;
        return newPath;
    }

    private Path currentShortestInUndone() {
        Path shortestPath = null;

        // when start
        if (doneVexes.isEmpty()) shortestPath = new Path(new int[]{from}, 0);

        // find out shortest path whose end is among undone list
        for (int target : paths.keySet()) {
            if (doneVexes.contains(target)) continue;
            Path path = paths.get(target);
            if (shortestPath == null || path.getDistance() < shortestPath.getDistance()) {
                shortestPath = path;
            }
        }
        return shortestPath;
    }

    public static class Path {
        private int[] path;
        private int distance;

        public Path(int[] path, int distance) {
            this.path = path;
            this.distance = distance;
        }

        public int getDistance() {
            return distance;
        }

        public int[] getPath() {
            return path;
        }

        public int end() {
            return path[path.length - 1];
        }
    }
}
